1. Field of the Invention
The invention relates in general to methods for generating integrated circuit (IC) placement and routing plans, and in particular to a computer-aided method for optimizing a placement plan to improve the likelihood that a routing plan based on the placement plan will satisfy all timing constraints.
2. Description of Related Art
An IC designer typically generates a hardware description language (HDL) netlist describing an IC in terms of the logical relations between the various IC input, output and internal signals to be conveyed by conductive networks (“nets”) to be formed within the IC. After creating the HDL netlist, the designer uses synthesis tools to convert the HDL netlist into a gate level netlist describing the IC as being formed by a set of instances of logic gates and other types of IC components for implementing the logic described by the HDL netlist. The gate level netlist indirectly describes each IC component by referring to it as an instance of a standard component (or “cell”) of that type described by an entry for that cell in a cell library, a database including a separate entry for each type of cell that a designer can incorporate into an IC. The cell library entry for each kind of cell provides information about that cell including, for example, its impedance characteristics and a description of the cell layout.
After using a synthesis tool to generate a gate level netlist, the designer typically uses placement and routing tools to generate an IC layout file including a placement plan indicating the position of each cell within the IC and a routing plan specifying the routing of the nets. The nets include conductors formed on one or more layers of the IC and vias extending between layers, and they may include buffers for amplifying signals as they travel between cells.
Most digital ICs employ register transfer logic wherein various synchronous logic blocks communicate with one another through latches, registers or other clocked devices. When a logic block receives its input signals and transmits its output signals through registers, state changes in its input and output signals can only occur at times coinciding with edges of the clock signals that clock its input and output registers. This makes the timing of signal edges passing between synchronous logic blocks highly predictable, thereby simplifying the task of coordinating their communications.
FIG. 1 illustrates a synchronous logic block including a set of gate G1–G8 receiving input signals for a latch L1 clocked by a clock signal CLK1 and transmitting its output signal through an output latch L2 clocked by a clock signal CLK2. Clock signals CLK1 and CLK2 will often be of similar frequency but of differing phase such that clock signal CLK2 will clock latch L2 with some predictable delay after an edge of CLK1 clocks latch L1. A “signal path” within an integrated circuit (IC) is a set of conductors and/or logic gates logically interconnecting two nodes. For example, a state change at a node A1 at the output of latch L1 occurring in response to an edge of clock signal CLK1 can cause a state change in signals at any of nodes A2–A4 at the inputs of latch L2. Thus, several signal paths connect node A1 to nodes A2–A4. More than one signal path can interconnect two nodes. For example, the following two signal paths link node A1 to node A3:    (nets N1, N2, N3, N4 and N5, gates G1, G2 G4, G7, and latch L2)    (nets N1, N2, N6, N4 and N5, gates G1, G3 G4, G7, and latch L2).
An IC designer will normally want the path delay through each signal path between any output of latch L1 and any input of latch L2 to be less than the period between edges of clock signals CLK1 and CLK2 so that after a CLK1 signal edge allows signals at the inputs of gates G1, G2, G5 and G8 to change state, all inputs to latch L2 will settle to their steady-state logic levels before the next CLK2 signal edge. The period between edges of the CLK1 and CLK2 signals therefore constitutes a “timing constraint” on every signal path between any output of latch L1 and any input of latch L2. The designer will typically employ a timing analysis tool to check an IC layout to determine whether all time-constrained paths will meet their timing constraints.
The delay through a signal path between any two nodes is the sum of the switching delays through all of the gates in the path and of the delays through the various nets included in the path. A computer-aided timing analysis tool can estimate the switching delay through each cell and the propagation delay through each section of a net in a signal path from the cell library description of that type of cell, from the resistance and capacitance of that net section and from the capacitance of any cell terminals that may be connected to that net section. The cell library tells the timing analysis tool the capacitance at each cell terminal, but since the resistance and capacitance of each conductor forming a section of a net depends on the dimensions of the conductor, the conductor's position with respect to other conductors, and the dielectric constant of the materials surrounding the conductor, a designer will typically employ a computer-aided resistance/capacitance (RC) extraction tool to process an IC layout to determine the resistance and capacitance of each conductor included in a net to provide the timing analysis tool with the impedance information it needs regarding the conductors included in each signal path to estimate the delay through the signal path.
When timing analysis shows that a layout fails to satisfy timing constraints on some signal paths, the designer may have to modify the layout to reduce path delays in those signal paths. In some cases, the designer may find it necessary to modify the cells forming the IC or modify the IC logic to eliminate timing constraints that are too difficult to satisfy. The placement and routing process can therefore be highly iterative and time-consuming, particularly when many signal paths are tightly constrained.
A typical placement algorithm tries to place interconnected cells close to one another to minimize path distances between them and to reduce routing congestion. Although its placement objectives help signal paths meet their timing constraints, such a placement tool does not directly consider timing constraints when placing cells. Since a computer can require much processing time to develop a detailed routing plan, one way to reduce the time required for the placement and routing process to converge on an acceptable layout is to employ a placement algorithm that takes timing constraints into account when producing a placement plan so that a routing tool will be more likely to produce a routing plan satisfying all timing constraints.
In one common approach for considering timing constraints when generating a layout, a designer first creates a timing budget allocating a separate portion of the timing constraint on each time-constrained signal path to each net included in that signal path. The designer then assigns a weight to each net indicating a priority that the placement algorithm is to place on keeping cells connected to that net near one another. When tightly constrained nets are given more weight, the placement algorithm will be biased toward keeping cells connected to the most tightly constrained nets close to one another. This approach addresses the timing closure problem in an indirect way by loosely transforming the timing closure problem into the problem of assigning net weights. But designers often find it difficult to determine how to allocate a signal path's timing constraint among the nets forming a signal path and to select an appropriate weight for each net. Allocating too large a portion of a time constraint to a net causes a placement algorithm to try to place cells connected to that net closer together than necessary and makes it more difficult for the algorithm to meet constraints on other nets. Assigning too little weight to a net can allow a placement algorithm to place cells connected to that net too far apart to meet timing constraints on signal paths including that net.
The invention relates to a method for determining how to modify a placement plan so that when a routing tool develops a detailed routing plan based on that placement plan, the resulting layout will be more likely to satisfying timing constraints on all signal paths.